﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.IO;
using System.Threading.Tasks;

namespace TesteC
{
    class ProgramV1
    {
        static string curFile = "";
        static void NotSoMain(string[] args)
        {
            /*
            DirectoryInfo d = new DirectoryInfo(@"C:\dev\coursera\knapsack\Knapsack\Knapsack\bin\Debug\data");
            FileInfo[] fs = d.GetFiles();
            for (int i = 0; i < fs.Length; i++)
            {
                FileInfo f = fs[i];

                curFile = f.FullName;
                doSolve(f.FullName);
            }*/
            doSolveV1("tmp.data");
            // doSolve("C:/dev/coursera/knapsack/Knapsack/Knapsack/bin/Debug/data/ks_19_0");
            
        }

        static void doSolveV1(string file)
        {
            using (StreamReader sr = new StreamReader(file))
            {
                using (StreamWriter sw = new StreamWriter("resp.txt"))
                {
                    int nItems = 0;
                    int knapSize = 0;
                    int[] values;
                    int[] weights;

                    string line = sr.ReadLine();
                    string[] s = line.Split();
                    nItems = int.Parse(s[0]);
                    knapSize = int.Parse(s[1]);
                    values = new int[nItems];
                    weights = new int[nItems];

                    int k = 0;

                    for (int kk = 0; kk < nItems; kk++)
                    //while (!sr.EndOfStream)
                    {
                        line = sr.ReadLine();
                        s = line.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
                        values[k] = int.Parse(s[0]);
                        weights[k] = int.Parse(s[1]);
                        k++;
                        //sw.WriteLine(sr.ReadLine());
                    }

                    System.Diagnostics.Stopwatch swKnap = new System.Diagnostics.Stopwatch();
                    swKnap.Start();
                    int bestVal = 0; int[] sol = new int[] { 1, 2, 3 };

                    solveKnapsackV1(knapSize, values, weights, out bestVal, out sol);

                    swKnap.Stop();


                    sw.WriteLine(bestVal.ToString() + " 1");
                    string ss = sol[0].ToString();
                    for (int i = 1; i < sol.Length; i++) ss += " " + sol[i].ToString();
                    sw.WriteLine(ss);
                }
            }
        }

        static void solveKnapsackV1(int knapSize, int[] values, int[] weights, out int bestVal, out int[] sol)
        {
            int[,] grid = new int[values.Length + 1, knapSize + 1];

            for (int capacity = 0; capacity < knapSize + 1; capacity++)
            {
                grid[0, capacity] = 0;
            }

            for (int itemId = 0; itemId < values.Length; itemId++)
            {
                for (int capacity = 0; capacity < knapSize + 1; capacity++)
                {
                    int valueIfITakeTheItem = 0;
                    int valueifIDoNotTakeTheItem = 0;

                    valueifIDoNotTakeTheItem = grid[itemId, capacity];

                    if (capacity - weights[itemId] >= 0)
                    {
                        valueIfITakeTheItem = grid[itemId, capacity - weights[itemId]] + values[itemId];
                    }

                    grid[itemId + 1, capacity] = Math.Max(valueIfITakeTheItem, valueifIDoNotTakeTheItem);
                }
            }

            bestVal = grid[values.Length, knapSize];

            //traceback
            int currentItem = values.Length;
            int currentCapacity = knapSize;

            sol = new int[values.Length];
            while (currentItem > 0)
            {
                if (grid[currentItem, currentCapacity] == grid[currentItem - 1, currentCapacity])
                {
                    sol[currentItem - 1] = 0;
                   
                }
                else
                {
                    sol[currentItem - 1] = 1;
                    currentCapacity -= weights[currentItem - 1];
                }
               
                currentItem--;
            }
            
        }
    }
}